package org.xingole.daily;

public class CheckIfNumberIsASumOfPowerOfThree {

     /*
      * Overview
      * 
      * We are given an integer n and need to determine if it can be written as a sum 
      * of distinct powers of 3. In other words, we want to know if we can choose some
      * of the numbers 3^0, 3^1, 3^2, ..., each used at most once, such that their sum
      * equals n. 
      * A generalized mathematical way to express this is:
      * 
      * n = 3^a[1] + 3^a[2] + ... + 3^a[k]
      * 
      * where all exponents a[1], a[2], ..., a[k] are unique and non-negative.
      *  
      */

     public boolean checkPowersOfThree(int n) {
          return checkPowersOfThreeHelper(0, n);
     }

     /*
      * Approach 1: Backtracking 
      *
      * An important observation is that we never need to use a power of 3 larger than
      * the given integer n, since that would immediately make the sum greater than n.
      * Since n can be as large as 10^7, the largest power of 3 we need to check is 
      * around 3^15, because log_3(10^7) := 15.
      *
      * Given this, we can use a backtracking approach to explore all possible ways to 
      * represent n as a sum of distinct powers of 3. At each step, we consider whether
      * to include or exclude the current power 3^power in our sum. 
      * 
      * For a given exponent power, we have two choices:
      *
      *   1. Include 3^power, reducing our target to n - 3^power and proceeding to the 
      * next exponent.
      *   2. Skip 3^power and try to form n using only higher powers.
      *
      */
     private boolean checkPowersOfThreeHelper( int power, int n ) {
          // Base case: if n becomes 0, we have successfully formed the sum.
          if ( n == 0 ) return true;

          // If the current power of 3 exceeds n, we cann't use it, so return false
          if ( Math.pow(3, power) > n ) {
               return false;
          }

          // Option 1: Include the current power of 3 and subtract it from n.
          boolean addPower = checkPowersOfThreeHelper(
               power+ 1, 
               n - (int) Math.pow(3, power) 
          );

          // Option2: Skip the current power of 3 and try with the next power
          boolean skipPower = checkPowersOfThreeHelper(power + 1, n);

          // Return true if either option leads to a valid solution
          return addPower || skipPower;
     }

     public static void main(String[] args) {
          
          CheckIfNumberIsASumOfPowerOfThree checker = new CheckIfNumberIsASumOfPowerOfThree();

          int n;

          // Example 1: 
          // Input: n = 12
          // Expected: true
          n = 12;
          System.out.println("\nExample 1 Output: " + checker.checkPowersOfThree(n));

     }

}
